﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;
using System.Text;
using System.Runtime.InteropServices;
using InformationRetrieval.Wildcard;
using InformationRetrieval.Normalization;
using System.Collections;
using InformationRetrieval.Tokenizer;

namespace InformationRetrieval.Indexer
{
    /// <summary>
    /// Inverted Index Class
    /// Capable of Adding Documents to the Index,
    /// Matching Search Queries with the Indexed Documents, and
    /// Persisting Indexed Documents to Hard Disk.
    /// </summary>
    public class InvertedIndex : IInvertedIndex
    {
        #region Fields

        /// <summary>
        /// Memory Limit for Index; When reached -> Disk Dump
        /// </summary>
        private const long _MemoryLimit = 1000000000; // ~ 1000 MB
        private long _InitialMemory = 0;

        /// <summary>
        /// Constants for Dumping Index to Hard Disk
        /// </summary>
        private const string _IndexDumpDirectory = @"\InvertedIndex\";
        private const string _DocumentRepositoryFileName = "documents";
        private const string _TermDictionaryFileName = "terms";
        private const string _TermFilePrefix = "term_";
        
        /// <summary>
        /// Dictionary for Index of Terms [Term, Term Postings]
        /// </summary>
        private Dictionary<string, TermPostings> _Index = new Dictionary<string, TermPostings>();

        /// <summary>
        /// Dictionary for Document IDs and Names (-> Repository)
        /// </summary>
        private Dictionary<int, string> _Documents = new Dictionary<int, string>();

        /// <summary>
        /// Dictionary for Terms (-> Dictionary)
        /// </summary>
        private SortedSet<string> _Terms = new SortedSet<string>();

        /// <summary>
        /// Counter for Indexed Documents; Used for Document IDs
        /// </summary>
        private int _DocumentCount = 0;

        /// <summary>
        /// Wildcard Index Object
        /// </summary>
        private IWildcardIndex _WildcardIndex = null;

        /// <summary>
        /// Normalizer Object
        /// </summary>
        private INormalizer _Normalizer = null;

        #endregion

        #region Constructors

        /// <summary>
        /// Default Constructor and Parametrized Constructors
        /// Accepts a Wildcard Index Object, a Normalizer Object, 
        /// Both of them or None of them.
        /// </summary>
        public InvertedIndex() : this(null, null) { }
        public InvertedIndex(IWildcardIndex wildcardIndex) : this(wildcardIndex, null) { }
        public InvertedIndex(INormalizer normalizer) : this(null, normalizer) { }
        public InvertedIndex(IWildcardIndex wildcardIndex, INormalizer normalizer)
        {
            // Either set Given Objects or set Dummy Objects
            this._WildcardIndex = wildcardIndex ?? new DummyWildcardIndex();
            this._Normalizer = normalizer ?? new DummyNormalizer();

            // Get Initial Memory from Garbage Collector
            this._InitialMemory = GC.GetTotalMemory(true);

            // Parse Document Repository from Hard Disk
            string filePath = Directory.GetCurrentDirectory() + InvertedIndex._IndexDumpDirectory;
            try
            {
                using (FileStream tmpStream = new FileStream(filePath + InvertedIndex._DocumentRepositoryFileName, FileMode.Open))
                {
                    using (BinaryReader tmpBinaryReader = new BinaryReader(tmpStream))
                    {
                        while (tmpBinaryReader.BaseStream.Position < tmpBinaryReader.BaseStream.Length)
                        {
                            int tmpDocumentId = tmpBinaryReader.ReadInt32();        // Document ID
                            string tmpDocumentName = tmpBinaryReader.ReadString();  // Document Name
                            this._Documents.Add(tmpDocumentId, tmpDocumentName);
                        }
                        tmpBinaryReader.Close();
                        tmpStream.Close();
                    }
                }
            }
            catch
            {
                // None
            }

            // Parse Term Dictionary from Hard Disk
            try
            {
                using (FileStream tmpStream = new FileStream(filePath + InvertedIndex._TermDictionaryFileName, FileMode.Open))
                {
                    using (BinaryReader tmpBinaryReader = new BinaryReader(tmpStream))
                    {
                        while (tmpBinaryReader.BaseStream.Position < tmpBinaryReader.BaseStream.Length)
                        {
                            string tmpTerm = tmpBinaryReader.ReadString();  // Term
                            this._Terms.Add(tmpTerm);
                        }
                        tmpBinaryReader.Close();
                        tmpStream.Close();
                    }
                }
            }
            catch
            {
                // None
            }

            // Count Documents
            this._DocumentCount = this._Documents.Count;
        } 

        #endregion

        #region Index Construction

        /// <summary>
        /// Adds a new Document to the Index.
        /// </summary>
        /// <param name="documentName">A distinct Document Name</param>
        /// <param name="documentTokens">A List of the Tokens in the Given Document</param>
        public void AddDocument(string documentName, IEnumerable<PositionedToken> documentTokens)
        {
            // Process the Given Document
            this.ProcessDocument(documentName, documentTokens);
        }

        /// <summary>
        /// Processes a given Document and Integrates it into the Index.
        /// </summary>
        /// <param name="documentName">A distinct Document Name</param>
        /// <param name="documentTokens">A List of the Tokens in the Given Document</param>
        private void ProcessDocument(string documentName, IEnumerable<PositionedToken> documentTokens)
        {
            int tmpDocumentId = 0;
            // If Document Name is already in Repository...
            if (this._Documents.ContainsValue(documentName))
            {
                // Get Key for Document Name
                foreach (KeyValuePair<int, string> kvp in this._Documents)
                {
                    if (kvp.Value.Equals(documentName))
                    {
                        tmpDocumentId = kvp.Key;
                    }
                }
            }
            else
            {
                // Increment Document Count and Add Document to Repository
                this._DocumentCount++;
                tmpDocumentId = this._DocumentCount;
                this._Documents.Add(tmpDocumentId, documentName);
            }

            // For all Terms in the parsed Document, Normalize and Index Term
            int termPosition = 0;
            foreach (var positionedToken in documentTokens)
            {
                termPosition = positionedToken.StreamPosition;
                string tmpTerm = _Normalizer.Normalize(positionedToken.Token);

                TermPostings tmpTermPostings;
                // If Term is not in Index...
                if (!this._Index.ContainsKey(tmpTerm))
                {
                    // Parse Postings for Term from Hard Disk
                    tmpTermPostings = new TermPostings(tmpTerm);
                    tmpTermPostings.ParseFromFile(  Directory.GetCurrentDirectory() + InvertedIndex._IndexDumpDirectory,
                                                    InvertedIndex._TermFilePrefix + tmpTerm );

                    // Add Term to Index
                    this._Index.Add(tmpTerm, tmpTermPostings);
                    this._Terms.Add(tmpTerm);
                }
                else
                {
                    if (!this._Index.TryGetValue(tmpTerm, out tmpTermPostings))
                    {
                        // Term Postings could not be found -> Continue with next Term
                        continue;
                    }
                }
                    
                // If Document ID is already in Postings List, Get Posting
                Posting tmpPosting;
                if (tmpTermPostings.PostingsList.TryGetValue(tmpDocumentId, out tmpPosting))
                {
                    // If Position is not in Posting already...
                    if (!tmpPosting.TermPositions.Contains(termPosition))
                    {
                        // Add Term Position to Posting, Increment Term Frequency
                        tmpPosting.TermPositions.Add(termPosition);
                        tmpPosting.TermFrequency++;
                    }
                }
                // If Document ID is not in Postings List...
                else
                {
                    // Create new Posting for current Document and Add new Positions List with current Term Position
                    tmpTermPostings.PostingsList.Add(   tmpDocumentId,
                                                        new Posting( 1, new SortedSet<int>() { termPosition } ) );
                }

                // If the Memory Requirement of the Index exceeds a certain Limit...
                long tmpCurrentMemory = GC.GetTotalMemory(false);
                if ( (tmpCurrentMemory - this._InitialMemory) >= InvertedIndex._MemoryLimit )
                {
                    System.Windows.Forms.MessageBox.Show("Memory limit reached");
                    
                    // Dump Index as Binary Text File to Specified Directory
                    this.DumpToFile();

                    // Clear Index
                    this._Index.Clear();
                    //this._Documents.Clear();

                    // Force Garbage Collection
                    GC.Collect();
                    GC.WaitForPendingFinalizers();
                }
            } // End For

            // Add Indexed Terms to Wildcard Index Object for later Wildcard Search Capability
            this._WildcardIndex.AddTerms(this._Terms);
        }

        /// <summary>
        /// Persist the Index
        /// </summary>
        public void Persist()
        {
            // Dump Index to File
            this.DumpToFile();
        }

        /// <summary>
        /// Dump Index to Binary Text Files on Hard Disk
        /// </summary>
        /// <returns>True or False</returns>
        private bool DumpToFile()
        {
            try
            {
                // Check for Dump Directory to Hard Disk
                string filePath = Directory.GetCurrentDirectory() + InvertedIndex._IndexDumpDirectory;
                // If Directory does not exist...
                if (!Directory.Exists(filePath))
                {
                    // Create Dump Directory
                    Directory.CreateDirectory(filePath);
                }

                // Dump Document Repository to Hard Disk
                using (FileStream tmpStream = new FileStream(filePath + InvertedIndex._DocumentRepositoryFileName, FileMode.Create))
                {
                    using (BinaryWriter tmpBinaryWriter = new BinaryWriter(tmpStream))
                    {
                        foreach (KeyValuePair<int, string> kvpJ in this._Documents)
                        {
                            tmpBinaryWriter.Write(kvpJ.Key);     // Document ID
                            tmpBinaryWriter.Write(kvpJ.Value);   // Document Name
                        }
                        tmpBinaryWriter.Close();
                        tmpStream.Close();
                    }
                }

                // Dump Term Dictionary to Hard Disk
                using (FileStream tmpStream = new FileStream(filePath + InvertedIndex._TermDictionaryFileName, FileMode.Create))
                {
                    using (BinaryWriter tmpBinaryWriter = new BinaryWriter(tmpStream))
                    {
                        foreach (string tmpTerm in this._Terms)
                        {
                            tmpBinaryWriter.Write(tmpTerm);     // Term
                        }
                        tmpBinaryWriter.Close();
                        tmpStream.Close();
                    }
                }

                int tmpPostingsListsCount = 0;
                int tmpIndexCount = _Index.Count;
                // Foreach Postings List of a Term...
                foreach (KeyValuePair<string, TermPostings> kvpJ in this._Index)
                {
                    string tmpTerm = kvpJ.Key;
                    // Dump Postings List to Hard Disk
                    TermPostings tmpTermPostings = kvpJ.Value;
                    tmpTermPostings.DumpToFile(filePath, InvertedIndex._TermFilePrefix + tmpTerm);

                    // Every 100 Postings Lists: Print Status Information
                    if (++tmpPostingsListsCount % 100 == 0)
                    {
                        Console.WriteLine("{0} / {1}", tmpPostingsListsCount++, tmpIndexCount);
                    }
                }
            }
            catch
            {
                return false;
            }

            return true;
        }

        #endregion

        #region Index Search

        /// <summary>
        /// Matches a Given Search Query against all Indexed Documents
        /// </summary>
        /// <param name="searchQuery">A String of Query Tokens</param>
        /// <returns>A List of [Term, Postings] Tupels</returns>
        public IEnumerable<KeyValuePair<string, Posting>> Find(string searchQuery)
        {
            // Split up the Search Query into Tokens
            string[] tmpSearchQueryTerms = searchQuery.ToLower().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);

            // Normalize the Search Query Tokens
            for (int i = 0; i < tmpSearchQueryTerms.Length; i++)
            {
                tmpSearchQueryTerms[i] = _Normalizer.Normalize(tmpSearchQueryTerms[i]);
            }

            SortedSet<int> overallResults = new SortedSet<int>();
            Dictionary<string, Posting> perDocumentResults = new Dictionary<string, Posting>();
            // Use the Search Query Tokens on the Index
            foreach (string tmpTerm in tmpSearchQueryTerms)
            {
                // Find the Postings List for the Current Term; 
                // If the Term contains Wildcards, Resolve them 
                TermPostings tmpTermPostings;
                foreach (var tmpWildcardTerm in this._WildcardIndex.Find(tmpTerm))
                {
                    // If Term is not in Index currently...
                    if (!this._Index.ContainsKey(tmpWildcardTerm))
                    {
                        // Parse Postings for Term from Hard Disk
                        tmpTermPostings = new TermPostings(tmpWildcardTerm);
                        tmpTermPostings.ParseFromFile(Directory.GetCurrentDirectory() + InvertedIndex._IndexDumpDirectory,
                                                        InvertedIndex._TermFilePrefix + tmpWildcardTerm);

                        // Add Term to Index in RAM
                        this._Index.Add(tmpWildcardTerm, tmpTermPostings);
                    }

                    // Get Postings List for Term from Index
                    if (this._Index.TryGetValue(tmpWildcardTerm, out tmpTermPostings))
                    {
                        // Get Matching Document Names and Postings
                        foreach (KeyValuePair<int, Posting> tmpDocument in tmpTermPostings.PostingsList)
                        {
                            Posting tmpPosting = tmpDocument.Value;
                            string tmpDocumentName = _Documents[tmpDocument.Key];

                            // If the Document is not in the Results List, Add the Document
                            if (!perDocumentResults.ContainsKey(tmpDocumentName))
                            {
                                perDocumentResults.Add(tmpDocumentName, tmpDocument.Value);
                            }
                            // If the Document is already in the Results List, Edit its Values
                            else
                            {
                                // Add Document Frequency for Weighting
                                perDocumentResults[tmpDocumentName].TermFrequency += tmpPosting.TermFrequency;
                                // Merge Postings Lists
                                perDocumentResults[tmpDocumentName].TermPositions.UnionWith(tmpPosting.TermPositions);
                            }
                        }
                    }
                }
            }

            // After this "perDocumentResults" should have a list of all documents containing at least a single searchword
            // Now we have to Sort them by their Term Frequency
            perDocumentResults = perDocumentResults.OrderByDescending(x => x.Value.TermFrequency).ToDictionary(x => x.Key, x => x.Value);

            return perDocumentResults.Take(10);
        }

        #endregion

        #region Helper Methods

        // none

        #endregion

        #region Statistics

        /// <summary>
        /// Number of documents in the inverted index
        /// </summary>
        public int DocumentCount { get { return this._Documents.Count; } }

        /// <summary>
        /// Number of unique, normalized terms in the inverted index
        /// </summary>
        public int TermCount { get { return this._Index.Count; } }

        /// <summary>
        /// Average length of the posting lists
        /// </summary>
        public int AvgPostingListLength
        {
            get
            {
                if (this._Index.Count > 0)
                    return (int)this._Index.Values.Average(x => x.PostingsList.Count);
                else return 0;
            }
        }

        /// <summary>
        /// Key-Value-Pair of the term with the longest posting list and
        /// the length of its posting list
        /// </summary>
        public KeyValuePair<string, int> MaxPostingListLength
        {
            get
            {
                if (this._Index.Count > 0)
                    return this._Index
                        .OrderByDescending(x => x.Value.PostingsList.Count)
                        .Select(x => new KeyValuePair<string, int>(x.Key, x.Value.PostingsList.Count))
                        .FirstOrDefault();
                else return new KeyValuePair<string, int>("Index Empty", 0);
            }
        }

        /// <summary>
        /// List of the 50 most common terms in the index, i.e. the terms
        /// with the longest posting lists
        /// </summary>
        public IEnumerable<string> MostCommonTerms50
        {
            get
            {
                return (from kvp in this._Index
                        orderby kvp.Value.PostingsList.Count descending
                        select kvp.Key).Take(50);
            }
        }

        /// <summary>
        /// List of the 50 least common terms in the index, i.e. the terms
        /// with the shortest posting lists
        /// </summary>
        public IEnumerable<string> LeastCommonTerms50
        {
            get
            {
                return (from kvp in this._Index
                        orderby kvp.Value.PostingsList.Count
                        select kvp.Key).Take(50);
            }
        }

        #endregion

        #region Inner Classes

        /// <summary>
        /// Postings for a Term [Overall Term Frequency, List of Postings]
        /// </summary>
        public class TermPostings
        {
            #region Properties

            //public int TermFrequency { get; set; }
            public string Term { get; set; }
            public SortedDictionary<int, Posting> PostingsList { get; set; }

            #endregion

            #region Constructors

            public TermPostings() : this("", null) { }
            public TermPostings(string term) : this(term, null) { }
            public TermPostings(SortedDictionary<int, Posting> postingsList) : this("", postingsList) { }
            public TermPostings(string term, SortedDictionary<int, Posting> postingsList)
            {
                this.Term = term;
                this.PostingsList = postingsList ?? new SortedDictionary<int, Posting>();
            }

            #endregion

            #region Methods

            /// <summary>
            /// Parse a Term File from Hard Disk and and Postings Lists to Current Object
            /// </summary>
            /// <param name="filePath">Path to the Term File</param>
            /// <param name="fileName">Name of the Term File</param>
            /// <returns>True or False</returns>
            public bool ParseFromFile(string filePath, string fileName)
            {
                try
                {
                    // Read Postings List from File
                    if (File.Exists(filePath + fileName))
                    {
                        using (FileStream tmpStream = new FileStream(filePath + fileName, FileMode.Open))
                        {
                            using (BinaryReader tmpBinaryReader = new BinaryReader(tmpStream))
                            {
                                this.PostingsList.Clear();
                                while (tmpBinaryReader.BaseStream.Position < tmpBinaryReader.BaseStream.Length)
                                {
                                    Posting tmpParsePosting = new Posting();
                                    int tmpParseDocumentId = tmpBinaryReader.ReadInt32();            // Document ID
                                    tmpParsePosting.TermFrequency = tmpBinaryReader.ReadInt32();     // Term Frequency

                                    // Term Positions in Document
                                    int tmpParsePosition = 0;
                                    tmpParsePosting.TermPositions = new SortedSet<int>();
                                    while ((tmpParsePosition = tmpBinaryReader.ReadInt32()) != -1)
                                    {
                                        tmpParsePosting.TermPositions.Add(tmpParsePosition);
                                    }

                                    // Add to Postings List
                                    this.PostingsList.Add(tmpParseDocumentId, tmpParsePosting);
                                }
                                tmpBinaryReader.Close();
                                tmpStream.Close();
                            }
                        }
                    }
                }
                catch
                {
                    return false;
                }
                
                return true;
            }

            /// <summary>
            /// Dump Postings List to a Binary Text File
            /// [DocumentId] [;] [TermFrequency] [;] [Positions] { [PositionX] [,] ... }
            /// </summary>
            /// <param name="filePath">Path to the Term File</param>
            /// <param name="fileName">Name of the Term File</param>
            /// <returns>True or False</returns>
            public bool DumpToFile(string filePath, string fileName)
            {
                // Write Serialized Postings List to Specified Directory
                try
                {
                    using (FileStream tmpStream = new FileStream(filePath + fileName, FileMode.Create))
                    {
                        using (BinaryWriter tmpBinaryWriter = new BinaryWriter(tmpStream))
                        {
                            foreach (KeyValuePair<int, Posting> kvpJ in this.PostingsList)
                            {
                                Posting tmpDumpPosting = kvpJ.Value;
                                tmpBinaryWriter.Write(kvpJ.Key);                     // Document ID
                                tmpBinaryWriter.Write(tmpDumpPosting.TermFrequency); // Term Frequency
                                
                                // Term Positions in Document
                                foreach (int tmpDumpPosition in tmpDumpPosting.TermPositions)
                                {
                                    tmpBinaryWriter.Write(tmpDumpPosition);
                                }

                                // End of Posting
                                tmpBinaryWriter.Write(-1);
                            }
                            tmpBinaryWriter.Close();
                            tmpStream.Close();
                        }
                    }
                }
                catch
                {
                    return false;
                }

                return true;
            }

            /// <summary>
            /// Calculate the Term Frequency for All Documents the Term occurs in
            /// </summary>
            /// <returns>Term Frequency</returns>
            public int GetTermFrequency()
            {
                int tmpTermFrequency = 0;
                // TODO: Optimize with LINQ
                foreach (KeyValuePair<int, Posting> kvp in this.PostingsList)
                {
                    tmpTermFrequency += kvp.Value.TermFrequency;
                }
                return tmpTermFrequency;
            }

            #endregion
        }

        /// <summary>
        /// Single Posting [Term Frequency for Document, List of Positions in Document]
        /// </summary>
        public class Posting
        {
            #region Properties

            public int TermFrequency { get; set; }
            public SortedSet<int> TermPositions { get; set; }

            #endregion

            #region Constructors

            public Posting() : this(0, null) { }
            public Posting(int termFrequency) : this(termFrequency, null) { }
            public Posting(SortedSet<int> positionsList) : this(0, positionsList) { }
            public Posting(int termFrequency, SortedSet<int> positionsList)
            {
                this.TermFrequency = termFrequency;
                this.TermPositions = positionsList ?? new SortedSet<int>();
            }

            #endregion
        }

        #endregion
    }
}
